package com.yoshino.leetcode.oneHundred.fifth;

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int n = matrix.length, m = matrix[0].length;
        int start = -1;
        if (m == 0) {
            return false;
        }
        // 找出需要遍历的行
        for (int i = 0; i < n; i++) {
            if (matrix[i][m - 1] >= target) {
                start = i;
                break;
            }
        }
        if (start == -1) {
            return false;
        }
        // 用二分法依次遍历行
        for (int i = start; i < n; i++) {
            if (matrix[i][0] <= target && binaryFindByInts(matrix[i], target)) {
                return true;
            }
        }
        return false;
    }

    private boolean binaryFindByInts(int[] matrix, int target) {
        int l = 0, r = matrix.length, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (matrix[mid] == target) {
                return true;
            } else if (matrix[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }

    public int minArray(int[] numbers) {
        int n = numbers.length;
        if (n == 1) {
            return numbers[n];
        }
        // 二分
        int l = 0, r = n - 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (numbers[r] > numbers[mid]) {
                // 右边递增
                r = mid;
            } else if (numbers[r] < numbers[mid]){
                l = mid + 1;
            } else {
                r--;
            }
        }
        return numbers[r];
        // 2 2 2 3 4 0 1
    }

    public char firstUniqChar(String s) {
        if (s.length() == 0) {
            return ' ';
        }
        int[] flags = new int[26];
        for (int i = 0; i < s.length(); i++) {
            flags[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (flags[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
}